package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution51 {

    public static void main(String[] args) {
        List<List<String>> lists = new Solution51().solveNQueens(4);
        for(List<String> list :lists){
            for(String temp : list){
                System.out.println(temp);
            }
            System.out.println("----------------------------");
        }
    }

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList();
        if(n <= 0) return res;
        List<String> tempList = new ArrayList();
        recurse(0, res, tempList, n);
        return res;
    }

    public void recurse(int count, List<List<String>> res, List<String> tempList, int n){
        if(count == n){
            res.add(new ArrayList(tempList));
            return;
        }

        for(int i = 0; i < n; i++){
            if(isOk(i, count, tempList, n)){
                tempList.add(columnStr(i, n));
                recurse(count + 1, res, tempList, n);
                tempList.remove(tempList.size() - 1);
            }
        }
    }

    public boolean isOk(int column, int row, List<String> tempList, int n){
        if(row == 0) return true;
        int left = column - 1;
        int right = column + 1;
        for(int i = row - 1; i >= 0; i--){
            String val = tempList.get(i);
            if(val.charAt(column) == 'Q'){
                return false;
            }

            if(left >= 0 && val.charAt(left) == 'Q'){
                return false;
            }
            left--;

            if(right <= n - 1 && val.charAt(right) == 'Q'){
                return false;
            }
            right++;
        }
        return true;
    }

    public String columnStr(int column, int n){
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++){
            if(i == column){
                sb.append("Q");
            }else{
                sb.append(".");
            }
        }
        return sb.toString();
    }
}
